package datastructure.queue.leetcode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @Description: 算法应用: 给定一个非空的整数数组，返回其中出现频率前 k 高的元素
 *              利用java的优先级队列完成
 * @author: Yang Qiang
 * @create: 2021-12-20 21:55
 */
public class Solution2 {
    public static void main(String[] args) {
        // 定义一个数组
        int[] num = {1,1,1,2,2,3};
        // 取出出现频率齐前两个数
        int k = 2;
        // 找打这两个数
        topicElm(num, k);
    }

    /**
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素
     *      1、统计数组中每个元素出现的频率
     *      2、将元素和出现的频率加工成一个对象放入到优先队列中
     *      3、获取优先队列中的元素并输出
     * @param nums: 目标数组
     * @param k: 出现频率前几
     */
    private static void topicElm(int[] nums, int k) {
        // 1、统计数组中每个元素出现的频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1);
            }
        }

        // 2、将元素和出现的频率加工成一个对象放入到优先队列中
        PriorityQueue<Freq> pq = new PriorityQueue();
        for (Integer key : map.keySet()) {
            // 优先级队列列名只能有我们需要的个数的元素, 也就是: 出现频率前 k 高的元素
            if (pq.size() < k){
                pq.add(new Freq(key, map.get(key)));

            // 如果正在循环的元素频率大于了我们优先队列队首的元素频率, 就需要进行进行出队并替换
            }else if (map.get(key) > pq.peek().freq){
                pq.remove();
                pq.add(new Freq(key, map.get(key)));
            }
        }

        // 3、获取优先队列中的元素并输出
        ArrayList<Object> list = new ArrayList<>();
        while (! pq.isEmpty()){
            list.add(pq.remove().e);
        }

        System.out.println(list);
    }


    /**
     * 元素和出现的频率加工成一个对象
     */
    public static class Freq implements Comparable<Freq> {
        // 哪个元素
        int e;
        // 元素出现的评率
        int freq;

        public Freq() {
        }

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        /**
         * 比较操作, 我们需要使用最小堆完成
         * 如果当前的对象, 比方法入参对象对象O小的话, 就返回一个正数
         * @param o
         * @return
         */
        @Override
        public int compareTo(Freq o) {
            return o.freq - this.freq;
        }
    }
}
